The present invention pertains to methods and systems involved in sequence estimation algorithms and, more particularly, to methods and systems for efficiently accumulating metrics associated with a sequence estimation algorithm, e.g., as part of the process of detecting radio signals.
The cellular telephone industry has made phenomenal strides in commercial operations in the United States as well as the rest of the world. Growth in major metropolitan areas has far exceeded expectations and is rapidly outstripping system capacity. If this trend continues, the effects of this industry's growth will soon reach even the smallest markets. Innovative solutions are required to meet these increasing capacity needs as well as maintain high quality service and avoid rising prices.
In mobile communication, the transmitted signal is often subjected to a time smearing effect created by the time dispersive nature of the channel, i.e., the air interface between a base station and a mobile station. The channel effects are estimated in the receiver part of a communication system, and used by the detector to aid in attempting to correctly deduce the information symbols that were transmitted thereto. A commonly used technique for deducing such received information symbols is known as Maximum Likelihood Sequence Estimation (MLSE) which, implemented using the Viterbi algorithm, is optimal for situations involving Additive While Gaussian Noise (AWGN).
An MLSE detector operates by selecting a known bit sequence closest to a received bit sequence. Because 2k bit sequences are involved (k being the number of data bits within a frame) in a typical MLSE detector, the system stores the 2k sequences for comparison with a received bit sequence. For a large value of k, this can be unwieldy. Viterbi simplified the maximum likelihood evaluation by noting that each of the states represented has only a finite number of possible predecessor states, and that only the path that agrees most with the received sequence (the minimum distance path) need be retained for each state. Trellis diagrams are commonly used to illustrate the concepts of paths and states associated with MLSE detecting, an example of which is provided as FIG. 1. For the simple four state trellis diagram depicted in FIG. 1, the characteristic used by Viterbi to simplify maximum likelihood evaluation may be understood by considering that each of the four states (00, 01, 10 and 11) has only two possible predecessor states, e.g., you can only reach the 00 state from a previous 00 state or a 10 state. Viterbi recognized that the likelihood evaluation could be significantly enhanced by using this factor in assessing possible paths through a trellis diagram.
Each possible path, or combination of state transitions, has an associated likelihood, or probability, of being correct. The probability of any given transition is based on a newly received value, in view of a succession of predecessor values. These transition probabilities are commonly referred to as metrics, and a succession of metrics are referred to as a path metric denoting the likelihood of a sequence of possible state transitions. Exemplary algorithms for computing metrics are discussed in detail below. However, it will be appreciated by those skilled in the art that the accumulation of metrics during MLSE detecting is a rather computationally intensive function. Since processing resources continue to be a valuable commodity in today's electronic devices, system designers have sought for ways to decrease the computational intensity of MLSE detecting without sacrificing quality.
One method for addressing this problem is described in an article authored by G. Ungerboeck, entitled “Adaptive Maximum Likelihood Receiver for Carrier Modulated Data Transmission Systems,” IEEE Trans. Commun., vol. COM-22, no. 4, pp. 624-535, May 1974, which applies two steps to reduce complexity. The first step is to expand the magnitude square term found in the metric computations and to eliminate terns that are common to all hypotheses. As a simple example, the term (a−b)2 can be expanded into a2−2ab+b2. If “a” does not depend on the hypothesized data, then the a2 term can be dropped from the metric computation.
The second step described by Ungerboeck is to re-arrange the order of the metric computations. With standard MLSE detecting, metrics are computed and updated based on successively received data samples. Each iteration of the Viterbi algorithm corresponds to a new received data sample. Using the second step as described by Ungerboeck, each iteration of the Viterbi algorithm corresponds to a newly transmitted symbol.
Another approach to reducing the complexity associated with the MLSE detecting is described in U.S. Pat. No. 5,499,272, entitled “Diversity Receiver for Signals with Multipath Time Dispersion”, to G. Bottomley, the disclosure of which is incorporated here by reference. Therein, joint MLSE detecting and diversity combining can be performed using a variant Ungerboeck form by expanding the metric expressions and collecting terms that correspond to the same hypothesized symbol.
Although MLSE detectors have been implemented through computationally efficient Viterbi schemes, e.g., using the Ungerboeck or variant Ungerboeck techniques described above, the MLSE detector might still be very computationally complex if large symbol alphabets are employed or if the number of required taps in the channel estimate is large. Both of these possibilities become more likely with next generation systems, e.g., EDGE which may employ 8-PSK modulation and a larger number of channel taps.
Accordingly, it continues to be desirable to make sequence estimation calculations more computationally efficient and to design detectors that will have a reduced MIPS requirement so as to free computational resources for other functionality.